package leetcode.editor.vscdev.hot100;
import leetcode.editor.utils.*;

public class lc21 {
    
}
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null){
            return list2; // list1走到头了返回list2连接
        } else if (list2 == null){
            return list1; // list2走到头了返回list1链接
        } else if (list1.val >= list2.val){
            // list2的当前节点值更小,要递归进行连接的是list2的下一个节点,回溯时把list2连上
            list2.next = mergeTwoLists(list1,list2.next);
            return list2; 
        } else {
            // 同理
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
    }
}